Sparsity Exploiting Erasure Coding for Resilient Storage and Efficient I/O Access in Delta based Versioning Systems

摘要

In this paper we study the problem of storing reliably an archive ofversioned data. Specifically, we focus on systems where the differences(deltas) between subsequent versions rather than the whole objects are stored -a typical model for storing versioned data. For reliability, we propose erasureencoding techniques that exploit the sparsity of information in the deltaswhile storing them reliably in a distributed back-end storage system, resultingin improved I/O read performance to retrieve the whole versioned archive. Alongwith the basic techniques, we propose a few optimization heuristics, andevaluate the techniques' efficacy analytically and with numerical simulations.